package 笔试题;

/**
 * @author 帅小伙
 * @date 2022/1/8
 * @description 代码是并查集完成的 ❌的
 * https://leetcode-cn.com/contest/weekly-contest-274/problems/maximum-employees-to-be-invited-to-a-meeting/
 */
public class Demo2127参加会议的最多员工数 {


    int parents[];
    int size[];
    int isUsed[];

    public int maximumInvitations(int[] favorite) {
        parents = new int[favorite.length];
        size = new int[favorite.length];
        isUsed = new int[favorite.length];

        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < favorite.length; i++) {
            union(i, favorite[i]);
        }

        int res = 0;
        for (int i = 0; i < size.length; i++) {
            if (res < size[i]) res = size[i];
        }
        return res;


    }

    public int find(int x) {
        if (parents[x] != x) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }

    public void union(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i != j && isUsed[x] < 2 && isUsed[y] < 2) {
            isUsed[x]++;
            isUsed[y]++;
            size[i] += size[j];
            parents[j] = parents[i];
        }

    }
}
